package imooc_math;
//基于size的优化
public class UF3 {
	public int[] parent;
	public int count;
	public int[] sz;//每个节点下的子节点个数
	public UF3(int n){
		count = n;
		parent=new int[n];
		for(int i=0;i<n;i++){
			parent[i] = i;
			sz[i] = 1; 
 		}
	}
	//让p跟q所在的组的所有数的id都相同
	public void union(int p,int q){
		int pRoot = find(p);
		int qRoot = find(q);
		if(pRoot == qRoot){
			return;
		}
		//parent[pRoot] = qRoot;		
		if(sz[pRoot] < sz[qRoot]){
			parent[pRoot] = qRoot;
			
			sz[qRoot] += sz[pRoot];			
		}else{
			parent[qRoot] = pRoot;
			sz[pRoot] += sz[qRoot];	
		}
	}
	//Quick find 时间复杂度：O(n)
	public int find(int p){
		while(parent[p] != p){
			p = parent[p];
		}
		return p;
	}
	public boolean isConnected(int p,int q){
		return find(p) == find(q);
	}




}
